<?php
/**
 * User: LRZ
 * Date: 2020/2/21
 * Time: 15:42
 */

/**
 *  812.最大三角形面积
 *
 *  标签：数学
 *
 *  给定包含多个点的集合，从其中取三个点组成三角形，返回能组成的最大三角形的面积。
 *
 *  示例:
 *      输入: points = [[0,0],[0,1],[1,0],[0,2],[2,0]]
 *      输出: 2
 *      解释: 这五个点如下图所示。组成的橙色三角形是最大的，面积为2。
 *
 *  注意:
 *      3 <= points.length <= 50.
 *      不存在重复的点。
 *      -50 <= points[i][j] <= 50.
 *      结果误差值在 10^-6 以内都认为是正确答案。
 *
 *  来源：力扣（LeetCode）
 *  链接：https://leetcode-cn.com/problems/largest-triangle-area
 *  著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */

$start = microtime(true);

$points = [[4, 6], [6, 5], [3, 1]];
$res    = largestTriangleArea($points);

$end = microtime(true);
print_r($res);
printf(' total run: %.2f s<br>' . 'memory usage: %.2f M<br> ', $end - $start, memory_get_usage() / 1024 / 1024);

function largestTriangleArea($points)
{
    $size     = count($points);
    $max_area = 0;
    foreach ($points as $i => $iValue) {
        for ($j = $i + 1; $j < $size; $j++) {
            for ($k = $j + 1; $k < $size; $k++) {
                $area     = getArea($points[$i], $points[$j], $points[$k]);
                $max_area = max($max_area, $area);
            }
        }
    }
    return $max_area;
}

function getArea($point1, $point2, $point3)
{
    return abs(($point1[0] * $point2[1] + $point2[0] * $point3[1] + $point3[0] * $point1[1]) -
            ($point1[1] * $point2[0] + $point2[1] * $point3[0] + $point3[1] * $point1[0])) * 0.5;
}